package java学习.leetcode.editor.cn;

import com.sun.source.tree.Tree;
import java学习.实训.day04.Test;
import java学习.算法.链表.Linkedlist;

import java.util.*;

/**
 * @author 刘世锦
 * 2022-11-27 22:21:01	 当前时间
 */
//给你一个二叉树的根节点 root ， 检查它是否轴对称。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [1,2,2,3,4,4,3]
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：root = [1,2,2,null,3,null,3]
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目在范围 [1, 1000] 内 
// -100 <= Node.val <= 100 
// 
//
// 
//
// 进阶：你可以运用递归和迭代两种方法解决这个问题吗？ 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 
// 👍 2200 👎 0

public class 对称二叉树{
	public static void main(String[] args) {
		Solution solution = new 对称二叉树().new Solution();
		TreeNode treeNode1= new TreeNode(1);
		TreeNode treeNode2= new TreeNode(2);
		TreeNode treeNode3= new TreeNode(2);
		TreeNode treeNode4= new TreeNode(3);
		TreeNode treeNode5= new TreeNode(3);
		treeNode1.left = treeNode2;
		treeNode1.right = treeNode3;
		treeNode2.right = treeNode4;
		treeNode3.right = treeNode5;
		System.out.println(solution.isSymmetric(treeNode1));
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
	// 复习 start 1-17

	/**
	 * 判断 if (left.val==right.val){ 直接 return true 是不对的，因为下面的左右子树此时还没有判断！ }
	 *
	 */
	public boolean isSymmetric(TreeNode root) {
		if (root==null){
			return true;
		}
		return compareLeftAndRight(root.left,root.right);

	}

	private boolean compareLeftAndRight(TreeNode left, TreeNode right) {
		if (left==null&&right==null){
			return true;
		}else if (left==null&&right!=null){
			return false;
		}else if(right==null&&left!=null){
			return false;
		} else if (left!=null&&right!=null){
			// 直接 return true 是不对的，因为下面的左右子树此时还没有判断！
			if (left.val!=right.val){
				return false;
			}
		}
		// 左子树的左节点与 右子树的右节点比较；
		// 左子树的右节点 与 右子树的左节点比较；
		return compareLeftAndRight(left.left,right.right)&&compareLeftAndRight(left.right,right.left);
	}


	/**
	 * 两个队列依次放入
	 * 		node1.left,node2.right
	 * 		node1.right,node2.left
	 */
	public boolean isSymmetric2(TreeNode root) {

		Queue<TreeNode> queue1 = new LinkedList<>();
		Queue<TreeNode> queue2 = new LinkedList<>();
		if (root!=null){
			queue1.offer(root.left);
			queue2.offer(root.right);
			while (!queue1.isEmpty()){
				TreeNode node1 = queue1.poll();
				TreeNode node2 = queue2.poll();
				if (node1==null||node2==null){
					return false;
				}
				if (node1.val!=node2.val){
					return false;
				}
				// 左右
				queue1.offer(node1.left);
				queue2.offer(node2.right);
				// 右左
				queue1.offer(node1.right);
				queue2.offer(node2.left);

			}
		}
		// root 为 null 就是对称的。
		return true;
	}



		// 复习 end





	/**
	 *  递归
	 *
	 */
	public boolean isSymmetricBFS(TreeNode root) {
		if (root==null) return true;
		return leftIsEqualRight(root.left,root.right);
	}

	private boolean leftIsEqualRight(TreeNode left, TreeNode right) {
		if (left==null&&right==null) return true;
		if (left==null||right==null||left.val!=right.val) return false;
		return leftIsEqualRight(left.left,right.right)&&leftIsEqualRight(left.right,right.left);
	}


	/**
	 * 每次弹出一对 比较元素是否equals
	 * 		1. 若存在其中一个为null || 值不相等： return false;
	 * 		2. 若两者皆为空： continue
	 * 以对称的方式加入队列：
	 * 		中左右 -- 中右左
	 * 		即： 左子树 左节点--右子树右节点
	 * 			左子树 右节点--右子树左节点
	 * 		要对称
	 */
	public boolean isSymmetricStack(TreeNode root) {
//		Stack<TreeNode> stack = new Stack<>();
		Deque<TreeNode> stack = new LinkedList<>();
		stack.push(root.left);
		stack.push(root.right);
		while (!stack.isEmpty()){
			TreeNode left = stack.pop();
			TreeNode right = stack.pop();
			if (left==null&&right==null){
				continue;
			}
			if (left==null&&right!=null||
			left!=null&&right==null||
			left.val!=right.val){
				return false;
			}
			stack.push(left.left);
			stack.push(right.right);
			stack.push(left.right);
			stack.push(right.left);
		}
		return true;
	}

	public boolean isSymmetricQueue(TreeNode root) {
		Queue<TreeNode> deque = new LinkedList<>();
			deque.offer(root.left);
			deque.offer(root.right);
			while (!deque.isEmpty()){
				TreeNode leftNode = deque.poll();
				TreeNode rightNode = deque.poll();
				if ((leftNode==null&&rightNode==null)){
					continue;
				}
//				if (leftNode == null && rightNode == null) {
//					continue;
//				}
				if (leftNode!=null&&rightNode==null||
					leftNode==null&&rightNode!=null||
					leftNode.val!=rightNode.val){
					return false;
				}
//				if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
//					return false;
//				}
				deque.offer(leftNode.left);
				deque.offer(rightNode.right);
				deque.offer(leftNode.right);
				deque.offer(rightNode.left);
		}
		return true;

	}
	public boolean isSymmetric3(TreeNode root) {
		Queue<TreeNode> deque = new LinkedList<>();
		deque.offer(root.left);
		deque.offer(root.right);
		while (!deque.isEmpty()) {
			TreeNode leftNode = deque.poll();
			TreeNode rightNode = deque.poll();
			if (leftNode == null && rightNode == null) {
				continue;
			}
//            if (leftNode == null && rightNode != null) {
//                return false;
//            }
//            if (leftNode != null && rightNode == null) {
//                return false;
//            }
//            if (leftNode.val != rightNode.val) {
//                return false;
//            }
			// 以上三个判断条件合并
			if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
				return false;
			}
			// 这里顺序与使用Deque不同
			deque.offer(leftNode.left);
			deque.offer(rightNode.right);
			deque.offer(leftNode.right);
			deque.offer(rightNode.left);
		}
		return true;
	}

	/** 先序：中左右  1 2 3 4 2 4 3
	 *  中序：左中右  3 2 4 1 4 2 3  2 3 1 2 3   3 2 1 2 3
	 *  后序：左右中  3 4 2 4 3 2 1
	 *  | 3
	 *    3 2 4 1 4 2 3
	 * @param root
	 * @return
	 */
		public boolean isSymmetricFail(TreeNode root) {
//    	中序遍历行不行？
//		不行
		Stack<TreeNode> stack = new Stack<>();
		ArrayList<Integer> list = new ArrayList<>();
		while (!stack.isEmpty()||root!=null){
			if (root!=null){
				stack.push(root);
				root = root.left;
			}else{
				root = stack.pop();
				list.add(root.val);
				root = root.right;
			}
		}
		System.out.println(list);
		boolean result = true;
		for (int i = 0,j=list.size()-1; i <=j; i++,j--) {
			if (!(list.get(i).equals(list.get(j)))){
				result = false;
				break;
			}
		}
		return result;
	}
}


//leetcode submit region end(Prohibit modification and deletion)

}
  class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode() {}
	TreeNode(int val) { this.val = val; }
	TreeNode(int val, TreeNode left, TreeNode right) {
		this.val = val;
		this.left = left;
		this.right = right;
	}

	  @Override
	  public String toString() {
		  return "TreeNode{" +
				  "val=" + val +
				  ", left=" + left +
				  ", right=" + right +
				  '}';
	  }
  }